package main

import "fmt"

/*
升序数组变为BST树
 */

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func sortedArrayToBST(left, right int, nums []int) *TreeNode {
	if left > right {
		return nil
	}
	mid := (left + right) / 2 + (left + right) % 2
	root := &TreeNode{Val:nums[mid]}
	root.Left = sortedArrayToBST(left, mid - 1, nums)
	root.Right = sortedArrayToBST(mid + 1, right, nums)

	return root
}

// 中序遍历二叉树
func OrderPrint(root *TreeNode) {
	if root == nil {
		return
	}
	OrderPrint(root.Left)
	fmt.Printf("%5d", root.Val)
	OrderPrint(root.Right)
}

func main() {
	nums := []int{1,2,3,4,5,6,7}
	root := sortedArrayToBST(0, len(nums) - 1, nums)

	// 打印
	OrderPrint(root)

}
